from typing import List


class Solution:
    def cheapestJump(self, nums: List[int], k: int) -> List[int]:
        size = len(nums)

        if nums[-1] == -1:
            return []

        dp = [float("inf")] * size
        next_step = [-1] * size
        dp[-1] = nums[-1]

        for i in range(size - 2, -1, -1):
            min_cost = float("inf")
            for j in range(i + 1, min(size, i + k + 1)):
                if nums[j] != -1:
                    cost = nums[i] + dp[j]
                    if cost < min_cost:
                        min_cost = cost
                        next_step[i] = j
            dp[i] = min_cost

        if dp[0] == float("inf"):
            return []

        ans = []
        now = 0
        while now != -1:
            ans.append(now + 1)
            now = next_step[now]

        return ans


if __name__ == "__main__":
    print(Solution().cheapestJump([1, 2, 4, -1, 2], 2))  # [1,3,5]
    print(Solution().cheapestJump([1, 2, 4, -1, 2], 1))  # []

    # 测试用例167/226
    print(Solution().cheapestJump([0, 0, 0, 0, 0, 0], 3))  # [1,2,3,4,5,6]

    # 测试用例213/226
    print(Solution().cheapestJump([0, -1, -1, -1, -1, -1], 5))  # []

    # 测试用例219/226
    print(Solution().cheapestJump([1, 2, 4, -1, 2], 1))  # []
